3. State programming

Today's topic

“State machine” and programming

Create your account on Scrapbox for taking the course.

You need a Google account (for GMail, etc.) to create a Scrapbox account.

You can also use your keio.jp account (G suite account).

What is a State?

Values representing current status

State machine

A machine whose state changes according to various events

Logic circuit, program, switch, etc.

Also called as “automaton”

State pattern

Handling state transition in a class

State transition examples

Games

Light switch

Programs

Ages, grades, positions

Monopoly

state = Piece position and property

http://gyazo.com/25c666c59b9a6443e46b4a9d4bd56a3f.png

State-aware programming

Complicated user interface

Communication protocols

Pattern matching

"Escape sequence" programming

Handling comments in programs

Roma-Kana conversion

Puzzle

Roma-Kana conversion

http://gyazo.com/caaf304022fdd558037e55e20bb83b4a.png

Escape sequence

Control display with special character sequences

Used on VT100 and compatible systems

Terminal.app

xterm

Erase the whole screen

code:c

main(){

printf("\x1b[2J");

printf("\x1b[0;0f");

}

Generate escape sequences using 'curses' library

http://gyazo.com/b79401fc6d7925e603d3450db23d7346.png

Human state transition

https://gyazo.com/45b640ee9804688b5ff4e9947394a108

State transition of a light toggle switch

http://gyazo.com/f8b9cf57199c5ed2501770dce007805c.png

State transition with hysteresis

http://gyazo.com/57efa56efe41ff54ff6c008e0ebbab70.png

TCP/IP state machine

https://gyazo.com/f5f8de9d6cdf2f8366d505397e971e30

State transition of a puzzle

http://gyazo.com/e91195d80701b5541bc71d9c147f3f05.png

State transition of detecting C comments

http://gyazo.com/c0d7354659a4eaa51af15edfa5c542b7.png

State transition of Japnese text input

http://gyazo.com/58b6691a0c3dac9880fcecac03c1e509.png

http://gyazo.com/05d1826ac1137cdb88d564ca8d3c6e73.png

Demo: Slime text input

https://www.youtube.com/watch?v=Ldyl5UbbSA8

All computers are state machines

State change by clock signals

Programming = state transition

CPU = complicated state transition machine

Combinational logic circuit

No state information

PLA (Programmable Logic Array)

http://gyazo.com/41bf1869e379af7498d83dd3ba2b4abe.png

Sequential circuit

State changes based on a clock signal

Current state is used in following calculation

http://gyazo.com/4018d6838089c0d3a10238efd8526f9a.png

Non-Deterministic Finite-state Automaton

Can move to multiple state

DFA

Simple

Easily implemented

Regular expressions can be easily converted to NDFA

(SUB)*SECTION

(abc|ade)

Converting NDFA to DFA

Any NDFA can be converted to DFA

Number of states increases

Example of conversion

(SUB)*SECTION

http://gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png

Conversion

http://gyazo.com/d9e5779fe46637b3fedf7783e0e2d1d3.png

Generated DFA

http://gyazo.com/c74f45af19228955d3a50cb796d6781b.png

Generated DFA

http://gyazo.com/c74f45af19228955d3a50cb796d6781b.png

Original NDFA

http://gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png

egrep command on Unix

Generate an NFA from a regular rexpression

Convert an NFA to DFA

Create a state transition table for DFA

Demo: egrep

Programming a DFA

Treat the execution context as the state

Use state variables

Use state transition tables

How do you program a state transition like this?

http://gyazo.com/05d1826ac1137cdb88d564ca8d3c6e73.png

Flowchart

http://gyazo.com/ba6a0d78000d76428b935d3a1d63c4af.png

Detecting comment areas in C

/* ... */

http://gyazo.com/e3114c38659d39bd4598116103724ee6.png

Using the execution context as the state

Program execution point represents the state

comment1.c

code:comment1.c

main()

{　

int c;

while(1){

c = get_c();

while(c == '/'){

c = get_c();

if(c == '*'){

printf("/*");

int done = 0;

while(! done){

c = get_c();

printf("%c",c);

while(c == '*'){

c = get_c();

printf("%c",c);

if(c == '/'){

done = 1;

c = get_c();

break;

}

}

}

}

}

}

}

Results

Using the execution position

OK if state transition is straightforward

Not good for complicted state transition

Difficult to understand even simpletransitions

Using state variables

States can be represented by the values of state variables

Use if/switch for checking states

Good for simple state transitions

Simple flags are state variables

Difficult to use many state variables consistently

Impossible to check all combinations

comment2.c

code:comment2.c

typedef enum {

S1, S2, C1, C2

} State;

State state = S1;

trans(int c)

{

switch(state){

case S1:

if(c == '/') state = S2;

break;

case S2:

if(c == '/') state = S2;

else if(c == '*'){

printf("/*");

state = C1;

}

else state = S1;

break;

case C1:

printf("%c",c);

if(c == '*') state = C2;

break;

case C2:

printf("%c",c);

if(c == '*') state = C2;

else if(c == '/') state = S1;

else state = C1;

break;

}

}

main()

{

char *s;

while(fgets(buf,1000,stdin)){

for(s=buf;*s;s++){

trans(*s);

}

}

}　　

State transition programming with a state transition table

States are represented as an integer value

Use a state transition table

By hand

Using a tool

State transition table

http://gyazo.com/adb22100f07d3c58e4d00192368589d9.png

comment3.c

code:comment3.c

enum {

S1, S2, C1, C2

};

int state = S1;

void init()

{

int i;

for(i=0;i<0x100;i++){

}　

state = S1;

}

main()

{

unsigned char *s;

init();

while(fgets(buf,1000,stdin)){

for(s=buf;*s;s++){

int oldstate = state;

if(oldstate == S2 && state == C1) printf("/*");

if(oldstate == C1 || oldstate == C2) printf("%c",*s);

}

}

}

State transition table generator

Converting a RegExp to a C program

lex

flex

General-purpose lexical analyzer generator

Former CEO of Google

Lex description example

code:lexsample.l

%option noyywrap

%option array

%{

int line=1;

%}

%state COMMENT

COMIN \/\*

COMOUT \*\/

%%

<INITIAL>^#.*$ {line++;}

<INITIAL>{COMIN} {BEGIN COMMENT;}

<COMMENT>. { printf("%s",yytext);}

<COMMENT>"\n" {line++;printf("%s",yytext);}

<COMMENT>{COMOUT} {BEGIN INITIAL;}

<INITIAL>. ;

<INITIAL>"\n" {line++;}

%%

int main(void){

yylex();

printf("%d lines read.\n",line);

return(0);

}

Example: lex

% lex lexsample.l

% cc -ll lex.yy.c

% ./a.out

Extended state transition diagram

Petri net

StateChart

Petri net

Tokens, braces, transitions

The token moves when tokens are ready at the input of a transition box

http://gyazo.com/ae0ec7c3b9aae443e9c5ca813f095297.png

Vending machine example

http://gyazo.com/ace3c9e593434fc2aa53e71cf7a37458.png

StateChart

Hierarchical state transition machine

Multiple states are represented as one state in an upper layer

Can be converted to conventional state machine

http://gyazo.com/65ff0aa39a149e6b44605730b0b5e2e3.png

A CD player specification in StateChart

http://gyazo.com/4d631d6d3d371c03dc5080f0f7a3a699.png

A CD player specification in StateChart

http://gyazo.com/77718e8f3a6b40d9df9e98bef2cbed0c.png

State transition of a Japanese text input system

http://gyazo.com/58b6691a0c3dac9880fcecac03c1e509.png

Implementations

Conversion tools for StateChart

Special tools required

Using StateChart without special tools

Represent a state as a function

Pass arguments to the parent state if they cannot be handled

State is represented as the current function

http://hondana.org/%E5%A2%97%E4%BA%95/1578201101 http://gyazo.com/e9a9a3673399c33937c1ebd8e3b68f8f.png

A CD player implemented in JavaScript

code:statechart.js

funcftion state_play(c){

switch(c){

case undefined: print("this is state_play"); return;

case 'stop_pressed': state = state_stopped; return false;

case 'pause_pressed': state = state_paused; return false;

default: return state_normal;

}

}

function state_paused(c){

switch(c){

case undefined: print("this is state_paused"); return;

case 'stop_pressed': state = state_stopped; return false;

case 'play_pressed': state = state_play; return false;

default: return state_normal;

}

}

function state_stopped(c){

switch(c){

case undefined: print("this is state_stopped"); return;

case 'play_pressed': state = state_play; return false;

default: return state_normal;

}

}

function state_normal(c){

switch(c){

case undefined: print("this is state_normal"); state_stopped();

case 'ff_pressed': state = state_forward; return false;

default: return false;

}

}

function state_forward(c){

switch(c){

case undefined: print("this is state_forward"); return;

case 'ff_released': state = state_play;return false;

default: return false;

}

}

function trans(c){

while(newstate = state(c)){

state = newstate;

}

state();

}

state = state_normal;

trans('play_pressed');

trans('ff_pressed');

trans('ff_released');

trans('stop_pressed');

trans('ff_pressed');

trans('ff_released');

What method should we use?

Statechart for complicated state transiton

State variable may be okay for simple programs

Try using statecharts

Documents are important

Exercise

Write a simple state transition program

Use literate programming style with HTML

Extract code from the HTML document